package com.leetcode.partition9;

import java.io.*;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2022/1/6 9:50
 */
public class LC847访问所有节点的最短路径aStar {

    private static final int N = 13, INF = 0x3f3f3f3f;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        int[][] graph = new int[n][];
        for (int i = 0; i < n; i++) {
            String[] s = reader.readLine().split("\\s+");
            int[] g = new int[s.length];
            for (int j = 0; j < s.length; j++) g[j] = Integer.parseInt(s[j]);
            graph[i] = g;
        }
        writer.write(shortestPathLength(graph) + "\n");
        writer.flush();
    }

    public static int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][1 << n];
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[i].length; j++) {
                dist[i][j] = INF;
            }
        }
        PriorityQueue<Node> heap = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.val, o2.val));
        //可以从任意一个节点开始，因此将从每一个进行入队
        for (int i = 0; i < n; i++) {
            int status = 1 << i;
            heap.add(new Node(eval(status, n), i, status));
            dist[i][status] = 0;
        }
        while (!heap.isEmpty()) {
            Node currNode = heap.poll();
            int status = currNode.status, dis = dist[currNode.curr][status];
            if (status == (1 << n) - 1) return dis;
            for (int v : graph[currNode.curr]) {
                int nextStatus = status | 1 << v;
                if (dist[v][nextStatus] > dis + 1) {
                    dist[v][nextStatus] = dis + 1;
                    heap.add(new Node(eval(nextStatus, n) + dis + 1, v, nextStatus));
                }
            }
        }
        return -1;
    }

    private static int eval(int status, int n) {
        //估价函数，当前状态和全1状态的区别作为代价
        int res = 0;
        for (int i = 0; i < n; i++) {
            if ((status >> i & 1) == 0) res++;
        }
        return res;
    }

    private static class Node {
        private int val;
        private int curr;
        private int status;

        public Node(int val, int curr, int status) {
            this.val = val;
            this.curr = curr;
            this.status = status;
        }
    }
}
